0001 // 0002 // BigUInt Division.swift 0003 // BigInt 0004 // 0005 // Created by Károly Lőrentey on 2016-01-03. 0006 // Copyright © 2016 Károly Lőrentey. All rights reserved. 0007 // 0008 0009 import Foundation 0010 0011 0012 extension BigUInt { 0013 //MARK: Division 0014 0015 /// Divide this integer by the digit `y`, leaving the quotient in its place and returning the remainder. 0016 /// 0017 /// - Requires: y > 0 0018 /// - Complexity: O(count) 0019 @warn_unused_result 0020 public mutating func divideInPlaceByDigit(y: Digit) -> Digit { 0021 precondition(y > 0) 0022 if y == 1 { return 0 } 0023 lift() 0024 0025 var remainder: Digit = 0 0026 for i in (0..<count).reverse() { 0027 let u = self[i] 0028 let q = Digit.fullDivide(remainder, u, y) 0029 self[i] = q.div 0030 remainder = q.mod 0031 } 0032 return remainder 0033 } 0034 0035 /// Divide this integer by the digit `y` and return the resulting quotient and remainder. 0036 /// 0037 /// - Requires: y > 0 0038 /// - Returns: (div, mod) where div = floor(x/y), mod = x - div * y 0039 /// - Complexity: O(x.count) 0040 @warn_unused_result 0041 public func divideByDigit
BigUInt Division.swift:43 BigUInt Radix Conversion.swift:109 (y: Digit) -> (div: BigUInt, mod: Digit) { 0042 var div = self 0043 let mod = div.divideInPlaceByDigit(y) 0044 return (div, mod) 0045 } 0046 0047 /// Divide this integer by `y` and return the resulting quotient and remainder. 0048 /// 0049 /// - Requires: `y > 0` 0050 /// - Returns: `(div, mod)` where `div = floor(self/y)`, `mod = self - div * y` 0051 /// - Complexity: O(count^2) 0052 @warn_unused_result 0053 public func divide
BigUInt Division.swift:66 BigUInt Prime Test.swift:91 if self.divideByDigit(p).mod == 0 {(y: BigUInt) -> (div: BigUInt, mod: BigUInt) { 0054 // This is a Swift adaptation of "divmnu" from Hacker's Delight, which is in 0055 // turn a C adaptation of Knuth's Algorithm D (TAOCP vol 2, 4.3.1). 0056 0057 precondition(y.count > 0) 0058 0059 // First, let's take care of the easy cases. 0060 0061 if self.count < y.count { 0062 return (0, self) 0063 } 0064 if y.count == 1 { 0065 // The single-digit case reduces to a simpler loop. 0066 let (div, mod) = divideByDigit(y[0]) 0067 return (div, BigUInt(mod)) 0068 } 0069 0070 // In the hard cases, we will simply perform the long division algorithm we 0071 // learned in school. It works by successively calculating the single-digit quotient of 0072 // the top y.count + 1 digits of x divided by y, replacing the top of x with the remainder, 0073 // and repeating the process one digit lower. 0074 // 0075 // The tricky part is that the algorithm needs to be able to do n+1/n digit divisions, 0076 // but we only have a primitive for dividing two digits by a single 0077 // digit. (Remember that this step is also tricky when we do it on paper!) 0078 // 0079 // The solution is that the long division can be approximated by a single fullDivide 0080 // using just the most significant digits. We can then use multiplications and 0081 // subtractions to refine the approximation until we get the correct quotient digit. 0082 // 0083 // We could do this by doing a simple 2/1 fullDivide, but Knuth goes one step further, 0084 // and implements a 3/2 division. This results in an exact approximation in the 0085 // vast majority of cases, eliminating an extra subtraction over big integers. 0086 // 0087 // Here is the code for the 3/2 division: 0088 0089 /// Return the quotient of the 3/2-digit division `x/y` as a single `Digit`. 0090 /// 0091 /// - Requires: (x.0, x.1) <= y && y.0.high != 0 0092 /// - Returns: The exact value when it fits in a single `Digit`, otherwise `Digit.max`. 0093 func approximateQuotient(x x: (Digit, Digit, Digit), y: (Digit, Digit)) -> Digit { 0094 // Start with q = (x.0, x.1) / y.0, (or Digit.max on overflow) 0095 var q: Digit 0096 var r: Digit 0097 if x.0 == y.0 { 0098 q = Digit.max 0099 let (s, o) = Digit.addWithOverflow(x.0, x.1) 0100 if o { return q } 0101 r = s 0102 } 0103 else { 0104 let (d, m) = Digit.fullDivide(x.0, x.1, y.0) 0105 q = d 0106 r = m 0107 } 0108 // Now refine q by considering x.2 and y.1. 0109 // Note that since y is normalized, q * y - x is between 0 and 2. 0110 let (ph, pl) = Digit.fullMultiply(q, y.1) 0111 if ph < r || (ph == r && pl <= x.2) { return q } 0112 0113 let (r1, ro) = Digit.addWithOverflow(r, y.0) 0114 if ro { return q - 1 } 0115 0116 let (pl1, so) = Digit.subtractWithOverflow(pl, y.1) 0117 let ph1 = (so ? ph - 1 : ph) 0118 0119 if ph1 < r1 || (ph1 == r1 && pl1 <= x.2) { return q - 1 } 0120 return q - 2 0121 } 0122 0123 // The function above requires that the divisor's most significant digit is larger than 0124 // Digit.max / 2. This ensures that the approximation has tiny error bounds, 0125 // which is what makes this entire approach viable. 0126 // To satisfy this requirement, we can simply normalize the division by multiplying 0127 // both the divisor and the dividend by the same (small) factor. 0128 let z = y.leadingZeroes 0129 let divisor = y << z 0130 var remainder = self << z // We'll calculate the remainder in the normalized dividend. 0131 var quotient = BigUInt() 0132 assert(divisor.count == y.count && divisor.last!.high > 0) 0133 0134 // We're ready to start the long division! 0135 let dc = divisor.count 0136 let d1 = divisor[dc - 1] 0137 let d0 = divisor[dc - 2] 0138 for j in (dc ... remainder.count).reverse() { 0139 // Approximate dividing the top dc+1 digits of `remainder` using the topmost 3/2 digits. 0140 let r2 = remainder[j] 0141 let r1 = remainder[j - 1] 0142 let r0 = remainder[j - 2] 0143 let q = approximateQuotient(x: (r2, r1, r0), y: (d1, d0)) 0144 0145 // Multiply the entire divisor with `q` and subtract the result from remainder. 0146 // Normalization ensures the 3/2 quotient will either be exact for the full division, or 0147 // it may overshoot by at most 1, in which case the product will be greater 0148 // than the remainder. 0149 let product = divisor.multiplyByDigit(q) 0150 if product <= remainder[j - dc ... j] { 0151 remainder.subtractInPlace(product, shift: j - dc) 0152 quotient[j - dc] = q 0153 } 0154 else { 0155 // This case is extremely rare -- it has a probability of 1/2^(Digit.width - 1). 0156 remainder.subtractInPlace(product - divisor, shift: j - dc) 0157 quotient[j - dc] = q - 1 0158 } 0159 } 0160 // The remainder's normalization needs to be undone, but otherwise we're done. 0161 return (quotient, remainder >> z) 0162 } 0163 } 0164 0165 //MARK: Division 0166 0167 /// Divide `x` by `y` and return the quotient. 0168 /// 0169 /// - Note: Use `x.divide(y)` if you also need the remainder. 0170 @warn_unused_result 0171 public func /(x: BigUInt, y: BigUInt) -> BigUInt { 0172 return x.divide(y).div 0173 } 0174 0175 /// Divide `x` by `y` and return the remainder. 0176 /// 0177 /// - Note: Use `x.divide(y)` if you also need the remainder. 0178 @warn_unused_result 0179 public func %(x: BigUInt, y: BigUInt) -> BigUInt { 0180 return x.divide(y).mod 0181 } 0182 0183 /// Divide `x` by `y` and store the quotient in `x`. 0184 /// 0185 /// - Note: Use `x.divide(y)` if you also need the remainder. 0186 public func /=(inout x: BigUInt, y: BigUInt) { 0187 x = x.divide(y).div 0188 } 0189 0190 /// Divide `x` by `y` and store the remainder in `x`. 0191 /// 0192 /// - Note: Use `x.divide(y)` if you also need the remainder. 0193 public func %=(inout x: BigUInt, y: BigUInt) { 0194 x = x.divide(y).mod 0195 }
BigUInt Division.swift:172 BigUInt Division.swift:180 BigUInt Division.swift:187 BigUInt Division.swift:194